#include "quickSort6.h"
#include "directSort7.h"
static void Swap(ElementType *A, ElementType *B){
    ElementType tmp = *A;
    *A = *B;
    *B = tmp;
}

ElementType Midian3(ElementType A[], int Left, int Right){
    int Center = (Left + Right) / 2;
    if (A[Left] > A[Center])
        Swap(A + Left, A + Center);
    if (A[Left] > A[Right])
        Swap(A + Left, A + Right);
    if (A[Center] > A[Right])
        Swap(A + Center, A + Right);
    
    Swap(A + Center, A + Right - 1);
    return A[Right - 1];
}

#define CUTOFF (3)
void QSort(ElementType A[], int Left, int Right){
    if(Right - Left > CUTOFF){
        ElementType pivot = Midian3(A, Left, Right);
        int i = 0, j = Right - 1;
        for(;;){
            while(A[++i] < pivot)
                ;
            while(A[--j] > pivot)
                ;
            if(i > j)
                break;
            Swap(A + i, A + j);
        }
        Swap(A + Right - 1, A + i);
        QSort(A, Left, i - 1);
        QSort(A, i + 1, Right);
    }else
        InsertionSort(A + Left, Right - Left + 1);
}

void QuickSort(ElementType A[], int n){
    QSort(A, 0, n - 1);
}